There are currently numerous possibilities for using autonomously operating mobile units. The uses of such mobile units include remote reconnaissance probes, mobile units that operate in dangerous areas, self-propelled industrial vacuum cleaners, transport vehicles in manufacturing and, last but not least, self-propelled robots. In order, however, to be able to carry out a meaningful job in an environment that is unknown a priori, an autonomous, mobile robot must both construct step-by-step a reliable map of its work environment and must also be able to localize itself with reference to this map at any given point in time. As a consequence of the extremely complex and unstructured environments in which such self-propelled units may be required to maneuver, their areas of use have been frequently limited to office and household environments. Since an a priori map is generally not available, such a self-propelled unit must be equipped with sensors which make it possible for the unit to flexibly interact with its environment. A few such sensors are, for example, laser range scanners, video cameras and ultrasound sensors.
A particular drawback of these mobile units is that the formation of the environment map and the localization of the mobile unit are dependent on one another. This results in the occurrence of various errors. First, such a prior art mobile unit measures the distance it has traversed from a starting position; second, it measures the distance from occurring obstacles with range sensors and enters these measurements into the environment map as landmarks. Since these errors accumulate and sum over longer distances, a meaningful maneuverability of the mobile unit is no longer established beyond a certain limit.
One method for the orientation of self-propelled mobile units in unknown environments is that the unit constructs a two-dimensional grid of its environment and provides individual cells of this grid with occupation values. The occupation values assigned per grid cell represent the occurrence of obstacles in the environment. Such a method of orientation of self-propelled units in grid maps is described in the publication "Histogrammic in Motion Mapping for Mobile Robot Obstacle Avoidance", IEEE Transactions on Robotics Automation, Vol. 7, No. 4, August 1991 by J. Borenstein and Yoram Koren.
Another problem results from the requirement of a necessary safety interval from articles in the environment. The route planning of the mobile unit is essentially defined by the maneuverability thereof, by the selected destination and by the obstacles on the route. The safety interval to be observed must be of such a nature that it impedes the mobility of the mobile unit to the least possible extent, so that it also remains maneuverable between obstacles located close to one another.